//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 
//
// 子数组 是数组中的一个连续部分。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出：6
//解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：nums = [5,4,-1,7,8]
//输出：23
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 105 
// -104 <= nums[i] <= 104 
// 
//
// 
//
// 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。 
// Related Topics 数组 分治 动态规划 
// 👍 4346 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution53 {
    /**
     * 解题思路：
     * 1.从数组的第二个元素开始，数组的最大长度=前一个元素的最大长度+当前元素。 如果前一个元素的最大长度小于0，那当前的最大元素就是当前元素
     * 2.dp[i] 表示数组第i个元素为结尾的最大子串值
     * 3.递推公式：
     * if(dp[i-1] <= 0) {
     *  dp[i] = nums[i];
     * } else {
     *  dp[i] = dp[i-1] + nums[i];
     * }
     * 4.初始值：dp[0] = nums[0];
     * 5.遍历顺序， 从左往右，从第二个元素开始遍历
     *
     *
     * 解答成功:
     * 			执行耗时:1 ms,击败了100.00% 的Java用户
     * 			内存消耗:50.7 MB,击败了9.77% 的Java用户
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int maxVal = nums[0];

        for(int i=1; i<nums.length; i++) {
            if(dp[i-1] <= 0) {
                dp[i] = nums[i];
            } else {
                dp[i] = dp[i-1] + nums[i];
            }
            if(maxVal < dp[i]) {
                maxVal = dp[i];
            }
        }

        return maxVal;



    }
}
//leetcode submit region end(Prohibit modification and deletion)
